Visual Basic Source Code/Visual Basic Source Code.iso/vbsource/vbdatabs/hash.cpp

C/C++ Source or Header | 1999-03-17 | 5.4 KB | 192 lines

// ------------------------------- //
// -------- Start of File -------- //
// ------------------------------- //
// ----------------------------------------------------------- //
// C++ Source Code File Name: hash.cpp
// Compiler Used: MSVC40, DJGPP 2.7.2.1, GCC 2.7.2.1, HP CPP 10.24
// Produced By: Doug Gaer
// File Creation Date: 02/14/1996
// Date Last Modified: 03/17/1999
// ----------------------------------------------------------- //
// ------------- Program description and details ------------- //
// ----------------------------------------------------------- //
/*
THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND.
THE ENTIRE RISK OF THE QUALITY AND PERFORMANCE OF THIS SOFTWARE
IS WITH YOU. SHOULD ANY ELEMENT OF THIS SOFTWARE PROVE DEFECTIVE,
YOU WILL ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR
CORRECTION.

The following program uses the class implementation of a symbol
table using a hashed lookup.
*/
// ----------------------------------------------------------- //
#include <string.h>

class TableData
{
public:
  TableData() { Next = 0; Data = 0; }

public:
  char *GetData() { return Data; }

public:
  char *Data;
  TableData *Next;
};

class HashTable : public TableData
{
public:
  HashTable(unsigned sz = 15);
  ~HashTable() { Clear(); }

private:
  HashTable(const HashTable &ob) { }      // Disallow copying
  void operator=(const HashTable &ob) { } // Disallow assignment

public:
  TableData *Find(char *str);
  TableData *Insert(char *str);
  int GetHashCode(char *str);
  void Clear();

private:
  TableData **tbl;
  unsigned size;
};

HashTable::HashTable(unsigned sz)
{
  if (sz < 0) sz = 15; // Do not allow a negitive table size
  tbl = new TableData *[size = sz];
  for (unsigned i = 0; i < sz; i++) tbl[i] = 0; // Null all the table nodes
}

void HashTable::Clear()
// Delete all the table nodes and release memory back to the heap
{
  for(unsigned i = 0; i < size; i++)
    {
      TableData *buf = Next;
      for(TableData *ptr = tbl[i]; ptr; ptr = buf)
    {
      buf = ptr->Next;    // Save next link before deleting it
      ptr->Next = 0;      // Null the Next pointer
      tbl[i] = ptr->Next; // Release node before deleting pointer holding
      delete ptr->Data;
      delete ptr;
    }
    }
}

int HashTable::GetHashCode(char *str)
{
  // Obtain a valid hash code for the table data
  int ii = 0;  // ii will represent the hash code
  char *pp = str;
  // Add each character of string p to ii using an exclusive OR
  while (*pp) ii = ii<<1 ^ *pp++;  // Shift left to avoid using only 1 byte
  if (ii < 0) ii = -ii; // Negate if less then zero
  ii %= size; // Divide with remainder and assign

  return ii;
}

TableData *HashTable::Find(char *str)
// Search the table for a matching node
{
  int ii = GetHashCode(str);

  // Search the table for the p string
  for (TableData *n = tbl[ii]; n; n = n->Next)
      if (strcmp(str, n->Data) == 0) return n;

  // Return a NULL if not found
  return 0;
}

TableData *HashTable::Insert(char *str)
// Insert a new node into the table
{
  int ii = GetHashCode(str);

  TableData *nn = new TableData;
  nn->Data = new char[strlen(str)+1]; // Allocate memory for the string
  strcpy(nn->Data,str); // Copy data into memory location

  if(tbl[ii] == 0) {
    // First node in the table
    tbl[ii] = nn;
    return nn;
  }
  else {
    // Next node in the table
    nn->Next = tbl[ii]; // Update Next pointer
    tbl[ii] = nn;       // New node is now the at head of the table
    return nn;
  }

  return 0; // Return 0 if Insert function fails
}

// Test program code starts here
// *********************************************************** //
#include <iostream.h>
#include <ctype.h>

// Create an array of items to load in the hash table
const int Items = 5; // Adjust this number if any more items are added
char *TblData[Items] = { "BIRD", "CAT", "COW", "DOG", "SNAKE" };

main()
{
  HashTable Table(Items);
  TableData *ptr;
  char buf[255];
  const char *ExitCode = "EXIT";

  // Add the entries to the hash table
  for(int Count = 0; Count < Items; Count++)
  {
    // Exit loop if Items is greater then the number of array elements
    if(TblData[Count] == 0) break;
    ptr = Table.Insert(TblData[Count]);
  }

  cout << "Enter the name of an animal to search for at the prompt." << endl;
  cout << "Enter EXIT to exit the program." << endl;

  do // Loop on the users input
    {
      cout << endl;
      cout << "Enter the name of an animal -> ";
      cin.getline(buf, sizeof(buf));
      cout << endl;

      // Convert all entries to upper case
      for(int i = 0; (buf[i] != ' ') && (buf[i] != '\0'); i++)
    buf[i] = toupper(buf[i]);

      if (strcmp(buf, ExitCode) == 0) break; // Break out of the loop

      cout << "Searching the table for a possible match..." << endl;
      ptr = Table.Find(buf);
      if(ptr)
    cout << "Found: " << ptr->GetData() << " in the hash table." << endl;
      else
    cout << "Did not find: " << buf << " in the hash table." << endl;

    }while(cin); // Test cin for each pass through the loop

  Table.Clear();

  return 0;
}
// ----------------------------------------------------------- //
// ------------------------------- //
// --------- End of File --------- //
// ------------------------------- //